package com.zj.leetcode.medium.dynamicProgramming;

/**
 * @program: algorithm
 * @description:
 * 一和零
 * 474 ones-and-zeroes
 * @author: Zhang Bo
 * @create: 2022-05-16 23:11:05
 **/
public class OnesAndZeroes{
    public static void main(String[] args) {
        Solution solution = new OnesAndZeroes().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findMaxForm(String[] strs,int m,int n) {
            if (strs.length == 0) {
                return 0;
            }
            int[][] dp =new int[m+1][n+1];
            for(String s :strs) {
                int zeros  = 0,ones = 0;
                for(char c:s.toCharArray()) {
                    if (c == '0') {
                        zeros++;
                    }else {
                        ones++;
                    }
                }
                for (int i = m; i >=zeros; i--) {
                    for (int j = n; j >= ones; j--) {
                        dp[i][j] = Math.max(dp[i][j], 1+dp[i-zeros][j-ones]);
                    }
                }
            }
            return dp[m][n];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}